package arr

import "sort"

/*
时间复杂度：O(N^2) 排序所花的时长为NlogN，但是遍历people切片需要n次，对people中每个元素的插入操作，需要O(n)的时间复杂度，所以将所有人插入到
	队列中需要N^2
空间复杂度:O(logN) 排序所需要的栈空间

套路:一般这种数对，还涉及排序的，根据第一个元素正向排序，根据第二个元素反向排序，或者根据第一个元素反向排序，根据第二个元素正向排序，往往能够简化解题过程。
 */
func reconstructQueue(people [][]int) [][]int {
	// 先根据身高降序排序，然后根据身高大于等于自己的数量升序排序
	sort.Slice(people, func(i, j int) bool {
		return people[i][0] > people[j][0] || people[i][0] == people[j][0] && people[i][1] < people[j][1]
	})
	var result [][]int
	// 当遍历到元素i时，前i-1个元素已经排好队了，由于在i后面的元素都是比i要矮的，所以后面元素无论插到哪个位置都不会对前i个元素产生影响（因为只有当
	// 一个大于等于自己的元素插入到自己前面才会产生影响）
	// 因此，在插入第i个元素时，如果people[i][1]为k，则只需要直接插入到位置k即可保证有该元素前面有k个数字大于等于自己
	for _, p := range people {
		idx := p[1]
		result = append(result[:idx], append([][]int{p}, result[idx:]...)...)
	}
	return result
}
